/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/5/8
 * Time: 22:23
 */
class BinaryTree {
    public static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        //
        public TreeNode(int value) {
            this.value = value;
        }
    }
    //
    public TreeNode createTree1() {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        return node1;
    }
    //
    public TreeNode createTree2() {
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;
        return node1;
    }
}
public class Solution {
    public static BinaryTree.TreeNode rootA = new BinaryTree().createTree1();
    public static BinaryTree.TreeNode rootB = new BinaryTree().createTree2();
    public static boolean isSubtree(BinaryTree.TreeNode rootA, BinaryTree.TreeNode subRoot) {
        if (rootA == null) {
            return false;
        }
        //如果两棵树相同
        if (isSameTree(rootA, subRoot)) {
            return true;
        }
        //如果subRoot和rootA左树相同
        if(isSubtree(rootA.left, subRoot)) {
            return true;
        }
        //如果subRoot和rootA右树相同
        return isSubtree(rootA.right, subRoot);
    }
    public static void main(String[] args) {
        System.out.println(isSubtree(rootA, rootB));

    }
    public static boolean isSameTree(BinaryTree.TreeNode rootA, BinaryTree.TreeNode rootB){
        //其中一个为空
        if ((rootA == null && rootB != null) || (rootA != null && rootB == null)) {
            return false;
        }
        //两个都为空
        if (rootA == null) {
            return true;
        }
        //两个都不为空
        if (rootA.value != rootB.value) {
            return false;
        }
        //判断左右子树是否相同
        return isSameTree(rootA.left, rootB.left) && isSameTree(rootA.right,rootB.right);
    }
}
